package com.atguigu.distributed.lock.leecode;

import java.util.ArrayList;

/**
 * 力扣中等078
 * 合并K个有序链表
 */
public class KLinkListMerge {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0) return null;
        int size = lists.length;
        return mergeList(lists,0,size-1);
    }

    private ListNode mergeList(ListNode[] lists,int left,int right){
        if(left == right) return lists[left];
        int mid = (left + right) /2;
        ListNode l1 = mergeList(lists,left,mid);
        ListNode l2 = mergeList(lists,mid+1,right);
        return mergerTwoListNode(l1,l2);
    }

    private ListNode mergerTwoListNode(ListNode l1,ListNode l2){
        ListNode result = new ListNode();
        ListNode dummy = result;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                result.next = l1;
                l1 = l1.next;
            } else {
                result.next = l2;
                l2 = l2.next;
            }
            result = result.next;
        }
        if(l1 != null){
            result.next = l1;
        }
        if(l2 != null){
            result.next = l2;
        }
        return dummy.next;
    }

}
